Many modem operating systems are built around a kernel, which provides a core set of functionality and services to allow programs to run on the computer hardware. The kernel includes code routines for handling traps. The operating system invokes such a routine (known as a trap routine) if an event occurs that is in some way unexpected or unanticipated.
There are a relatively wide variety of circumstances that can lead to a trap routine being called. One example is a page fault, when a process attempts to access a virtual address, and the memory management unit (MMU) does not currently contain a mapping from this virtual address to a real physical memory location. This can occur if there is not enough room within the MMU, more particularly the translation lookaside buffer (TLB), to store the relevant mapping. In this case, the correct mapping must be retrieved into the TLB, in order to provide the desired association between the requested virtual address and the corresponding physical memory location. Alternatively, a page fault may arise when a requested virtual address does not lie within any mapped region (this of course will normally lead to program error).
Another circumstance in which a trap can be generated is where there is some instruction error detected by a processor. Examples of this situation would be an attempt to divide by zero, or to execute an instruction requiring a higher privilege level than possessed by the relevant process.
The above two classes of traps can be regarded as synchronous, in that they occur in the course of normal program flow. On the other hand, many traps can also be generated asynchronously. Typically these are initiated by some form of hardware interrupt. For example, such an interrupt may be used to indicate that the user has hit a key on a computer terminal; that a disk unit has successfully retrieved some requested data; or that another processor in a multi-processing system has made some form of request. A further form of asynchronous event that can invoke trap code is the receipt of a data communication from an external source, such as a packet over a network.
A computing system often has to handle a very high rate of traps, given the wide range of situations in which they can arise. For example, a processor in a typical server may receive thousands of trap events per second. It will be recognised therefore that the performance of trap code can be highly significant for the overall performance of the machine. Note that this impact is both direct, as programs have to wait for trap routines to complete, and also indirect, as trap routines consume machine resources that could otherwise be employed by other programs.
Trap routines are therefore normally written in assembly code for the machine on which they are to be run in order to maximise speed. In addition, this allows low-level operations to be performed directly with the hardware, which can be necessary given the purpose of a trap routine, for example to process interrupts.
It is also very important that trap routines behave correctly. This is not only because, as low level code, trap routines bypass many of the safeguards that are provided for normal programs, but also because they run in kernel space, and so have relatively high privileges. It will be appreciated therefore that a misbehaving trap routine can easily cause the complete system to crash, and potentially result in the loss of data as well.
In view of the above, understanding the operation of a trap routine is very important, both to ensure correct behaviour, and also for performance reasons (to see if there is any way in which the overall speed of the trap routine can be improved). A typical way to do this is to instrument the code. Such instrumentation enables the recording of various state values within the code for subsequent analysis, in order to get a clearer understanding of the operation of the code. This can then assist with both defect correction and also performance analysis and optimisation (these activities will be collectively referred to herein as debugging).
For programs in a higher level language, a common way to instrument code is simply to include output statements in various locations. These can then be used to print or save to disk the values of selected variables during the running of a program. However, the instrumentation of trap code is a rather more challenging proposition. Thus there are normally significant constraints imposed on trap code regarding the nature of operations that can be performed within a trap routine. This helps to reduce the likelihood of problems arising from execution of the trap routine itself. Thus should an attempt to write data lead inadvertently to another trap routine being called, this may only further exacerbate the situation.
(Note that it is not normally possible to avoid entirely nested trap routines, i.e. where one trap routine triggers another. Nevertheless, it is generally desirable to try to minimise the occurrence of such nesting in order to avoid certain problems, such will be described in more detail below).
Many systems therefore do not support the instrumentation of trap code via simple write statements. Rather, it is known to provide a special-purpose macro that can be used instead to output data from trap code. However, a complication can arise here, in that many processors require the output address for a write operation to be stored in a register. This restriction is particularly true in reduced instruction set computing (RISC) system, since RISC processors tend to have relatively short-length instructions. In such circumstances, there is no room to incorporate the output address for a write or store instruction into the instruction itself, hence the need for this to be available to the processor in a register instead. (In contrast, in some complex instruction set computing (CISC) processors, the instructions can be much longer, and so are able to directly incorporate the address for a particular write operation). Thus for a RISC environment, or other system in which output addresses must be stored within a register, it is necessary to find a free register to store an output address before a write operation can be performed.
It is known to provide a processor with registers for use by trap code. The primary reason for this is that when trap code is initiated, the previous processing state must be saved, since the invocation of the trap routine necessitates a change of processing direction compared with the immediately preceding instructions. In general therefore, the processor has to save the state of the process that was executing immediately prior to receipt of the trapped event. This then allows the process to be safely restored after the trap routine has completed.
It will be appreciated that this is analogous to a function call, where the state of the calling function is saved on the program stack when the function is invoked. Thus the program stack maintains state information when dropping from a first program function into a second program function. This ensures that when the second program function has completed, the first function can be revived in its correct state (as of the time the second function was initiated). A program stack can typically save a whole series of states, thereby allowing function calls to be nested one within the other.
In theory the main program stack could also be used for saving state on entry into trap routines. However, this turns out to be rather unattractive for performance reasons. This is because a conventional stack facility may save more context than is needed for the execution of a simpler trap routine. Moreover, use of the stack may trigger further traps, for instance when the expansion of a stack across a page-boundary itself causes a page-fault trap. Consequently, trap routines typically try to use the registers mentioned above for storing state information to allow the previous program state to be restored at the end of the trap code. The use of such registers rather than the program stack by the processor helps to ensure that the trap-code executes quickly.
However, the situation becomes more complicated where one trap gets called from within another trap (i.e. trap nesting). An example of this is where a trap routine needs to access a particular virtual address that is not currently mapped in the TLB, since this then results in another trap. Thus a hierarchical set of trap routines can be invoked, in analogous fashion to the stacked function calls mentioned above. This can lead to a situation where the nesting or processing involved is too complex to be accommodated by the registers available to the processor. In such circumstances, the use of the program stack to store state data becomes inevitable.
Returning now to the instrumentation of trap code, it will be recalled that in a RISC environment and on certain other machines, a write operation requires the relevant output address to be stored in a register. In fact, the instrumentation macro for a trap routine typically utilises a circular buffer in memory for outputting data, and this then needs two free registers in order to operate properly: one for storing the base location of the buffer, and one for storing the current write location within the buffer (i.e. corresponding to its fill level).
In theory, the registers available to the processor for storing state information during trap routines might serve such a purpose (i.e. storing one or more output addresses). However, this is problematic, because it is difficult to know with certainty whether or not a particular register is free. Rather, a register accessible to a trap routine may already be being used to store state information for nested trap routines or from the previously executing program. Thus any attempt to store an output address in a register may inadvertently overwrite important state information for preceding code, and thereby prevent proper operation of the system once the trap routine has completed.
Of course, the instrumentation code could try to force the trap routines to utilise the program stack for saving their state information, since this would then free up the registers to store output addresses. However, it is highly undesirable for instrumentation to have such a major impact on code under investigation, since this can easily lead to a significant divergence between the behaviour of the instrumented code and of the non-instrumented code. This in turn can prevent proper understanding and analysis of the non-instrumented code, and so undermine the very purpose of the instrumentation itself.